package kyssion.leetcode.num1_50;

public class code42_接雨水 {
    public static void main(String[] args) {
        new code42_接雨水().trap(
                new int[]{
                        10,8,9,7,8,6,7,5,6,4,5
                }
        );
    }

    /**
     * 我这里有点想歪了, 这个是我第一种的解决办法,但是是错的, 本来的想法是构造一个数据列,可以让,当前的
     * 位置index 能直接找到他的右边界
     * 但是确实没有在最坏时间负载度是O(n)的情况下找到比如
     * 10,8,9,7,8,6,7,5,6,4,5
     * 所以记录一下思路就好了
     * 我的思路就是找到波峰, 通过记录所有的波峰就能知道所有的和了
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int[] map = new int[height.length];
        int index = 0;
        for (int a = height.length - 1; a >= 0; a--) {
            if (a == height.length - 1 && height[a - 1] <= height[a]) {
                map[index] = height.length - 1;
                index++;
            } else if (a == 0 && height[a + 1] <= height[a] ||
                    height[a] >= height[a - 1] && height[a] > height[a + 1]) {
                while (index > 0) {
                    if (map[index - 1] != height.length - 1 && height[map[index - 1]] < height[a]) {
                        index--;
                    } else {
                        break;
                    }
                }
                map[index] = a;
                index++;
            }
        }
        return 1;
    }

    /**
     * 最佳姿势,其实是一种思维,边界点和临界值的灵活运用,这个题的思想和
     *
     * @param height
     * @return
     */
    public int trap2(int[] height) {
        int maxIndex = 0;
        int max = 0;
        for (int a = 0; a < height.length; a++) {
            if (height[a] > max) {
                max = height[a];
                maxIndex = a;
            }
        }
        int sum = 0;
        int before = 0;
        for (int a = 0; a < maxIndex; a++) {
            if (height[a] > before) {
                before = height[a];
            } else {
                sum += before - height[a];
            }
        }
        before = 0;
        for (int a = height.length - 1; a > maxIndex; a--) {
            if (height[a] > before) {
                before = height[a];
            } else {
                sum += before - height[a];
            }
        }
        return sum;
    }
}
